// 给定一个整数矩阵，找出最长递增路径的长度。

// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

// 示例 1:

// 输入: nums = 
// [
//   [9,9,4],
//   [6,6,8],
//   [2,1,1]
// ] 
// 输出: 4 
// 解释: 最长递增路径为 [1, 2, 6, 9]。
// 示例 2:

// 输入: nums = 
// [
//   [3,4,5],
//   [3,2,6],
//   [2,2,1]
// ] 
// 输出: 4 
// 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

#include <vector>
#include <queue>

using namespace std;

/* 记忆化深度优先搜索
将矩阵看成一个有向图，如果相邻节点值不等，则从较小值指向较大值。
问题转化成在有向图中寻找最长路径
朴素深度优先搜索时间复杂度过高，因为相同单元格会被访问多次，重复计算
同一单元格对应的最长递增路径的长度是固定不变的，使用记忆化数组memo将已经计算过的结果缓存
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
class Solution {
public:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows{0};
    int cols{0}; 
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        rows = matrix.size();
        cols = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(cols, 0));
        int res{0};
        for (int i{0}; i < rows; ++i) {
            for (int j{0}; j < cols; ++j) {
                res = max(res, dfs(matrix, i, j, memo));
            }
        }
        return res;
    }
    int dfs(const vector<vector<int>>& matrix, int row, int col, vector<vector<int>>& memo) {
        if (memo[row][col] != 0) {
            return memo[row][col];
        }
        ++memo[row][col];
        for (int i{0}; i < 4; ++i) {
            int newRow = row + dirs[i][0];
            int newCol = col + dirs[i][1];
            if (newRow >= 0 && newRow < rows &&
                newCol >= 0 && newCol < cols &&
                matrix[newRow][newCol] > matrix[row][col])
            {
                memo[row][col] = max(memo[row][col], dfs(matrix, newRow, newCol, memo) + 1);
            }
        }
        return memo[row][col];
    }    
};

/* 拓扑排序
如果一个单元格的值比它的所有相邻单元格的值都要大，那么这个单元格对应的最长递增路径是 1 ，单元格的出度是 0。
基于出度的概念，可以使用拓扑排序求解。从所有出度为 0 的单元格开始广度优先搜索，每一轮搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为 0 的单元格加入下一层搜索。当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度。
时间复杂度：O(mn)
空间复杂度：O(mn)
*/
class Solution {
public:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int rows{0};
    int cols{0};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        rows = matrix.size();
        cols = matrix[0].size();
        vector<vector<int>> outDegrees(rows, vector<int>(cols, 0));
        for (int i{0}; i < rows; ++i) {
            for (int j{0}; j < cols; ++j) {
                for (int k{0}; k < 4; ++k) {
                    int newRow = i + dirs[k][0];
                    int newCol = j + dirs[k][1];
                    if (newRow >= 0 && newRow < rows &&
                        newCol >= 0 && newCol < cols &&
                        matrix[newRow][newCol] > matrix[i][j])
                    {
                        ++outDegrees[i][j];
                    }
                }
            }
        }
        queue<pair<int, int>> q{};
        for (int i{0}; i < rows; ++i) {
            for (int j{0}; j < cols; ++j) {
                if (outDegrees[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }
        int res{0};
        while (!q.empty()) {
            ++res;
            int size = q.size();
            for (int i{0}; i < size; ++i) {
                pair<int, int> cell = q.front();
                q.pop();
                int row = cell.first;
                int col = cell.second;
                for (int k{0}; k < 4; ++k) {
                    int newRow = row + dirs[k][0];
                    int newCol = col + dirs[k][1];
                    if (newRow >= 0 && newRow < rows &&
                        newCol >= 0 && newCol < cols &&
                        matrix[newRow][newCol] < matrix[row][col])
                    {
                        --outDegrees[newRow][newCol];
                        if (outDegrees[newRow][newCol] == 0) {
                            q.push({newRow, newCol});
                        }
                    }
                }
            }
        }
        return res;
    }
};